package com.zjsru.oneDay202206;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: likew
 * @Date: 2022/6/30
 * 质数排列
 * 请你帮忙给从 1 到 n 的数设计排列方案，使得所有的「质数」都应该被放在「质数索引」（索引从 1 开始）上；你需要返回可能的 方案总数。
 * 输入：n = 5
 * 输出：12
 * 解释：举个例子，[1,2,5,4,3] 是一个有效的排列，但 [5,2,3,4,1] 不是，因为在第二种情况里质数 5 被错误地放在索引为 1 的位置上。
 * 由于答案可能会很大，所以请你返回答案 模 mod 10^9 + 7 之后的结果即可。
 *
 *
 * n =5 质数 3，5 有效排列结果数组下标叫索引（不是0是从1开始） 那么什么叫质数索引 ，下标的值为质数的就是质数索引的位置
 * 本例中 第三位，第五位是质数索引。 由题解可知：使得所有的「质数」都应该被放在「质数索引」上 0 0 质 0 质 3，5只能放在最终结果的第三个，第五个位置。
 * 00305 00503 [5,2,3,4,1] 3在质数索引的位置上而5不在 所以错误。
 * 也就是说 质数只能在质数的位置上排列组合 非质数只能在非质数的位置上排列组合 结果 = 质数组合*非质数组合
 * 所以求出质数个数，非质数的个数 他俩阶乘相乘就行。
 *
 */
public class numPrimeArrangements {
    static int MOD = (int)1e9+7;
    static List<Integer> list = new ArrayList<>();
    //在100个数中找到质数，存入集合
    static {
        for (int i = 2; i <= 100; i++) {
            boolean ok = true;
            for (int j = 2; j * j <= i; j++) {
                if((i % j) == 0) ok = false;
            }
            if(ok) list.add(i);
        }
    }
//    用二分查找到一共有几个质数
    public int numPrimeArrangements(int n) {
        int l = 0, r = list.size() - 1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(list.get(mid) <= n) l = mid;
            else r = mid - 1;
        }
        //a=质数格数，b= 非质数个数
        int a = r + 1, b = n - a;
        long ans = 1;
        for (int i = b; i > 1; i--) {
            ans = ans * i % MOD;
        }
        for (int i = a; i > 1; i--) {
            ans = ans * i % MOD;
        }
        return (int)ans;
    }
    
    public static void main(String[] args) {
        numPrimeArrangements numPrimeArrangements = new numPrimeArrangements();
        int n = 5;
        System.out.println(numPrimeArrangements.numPrimeArrangements(n));
    }
}
